package com.huawei.tree.AVL;

//平衡二叉排序树
public class AVL {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    //添加节点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;//如果root为空，直接让root指向node
        }else {
            root.add(node);
        }
    }

    //中序遍历
    public void midOrder() {
        if (root != null) {
            root.minOrder();
        }else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

    //查找要删除的节点
    public Node search(int value) {
        if (root == null) {
            return null;
        }else {
            return root.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }else {
            return root.searchParent(value);
        }
    }

    /**
     * @Name: 删除节点方法调用
     * @Author: GaoJian
     * @Date: 2022/4/23 23:19
     * @Description: 参数：传入的节点 返回值：返回以node为根节点的二叉排序树的最小节点的值
     * 任务1：返回以node为根节点的二叉排序树的最小节点的值
     * 任务2：删除node为根节点的二叉排序树的最小节点
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //循环的查找左子节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这是target就指向最小节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }

    //删除节点：添加节点方法分析（大于等于、小于当前节点值 -> 左子树、右子树递归添加） ->  删除节点方法一些步骤不需要判断节点值大小
    public void delNode(int value) {
        if (root == null) {
            return;
        }else {
            //1、需要先找到要删除的节点 targetNode
            Node targetNode = search(value);
            //如果没有找到要删除的节点
            if (targetNode == null) {
                return;
            }
            //如果我们发现当前的二叉排序树只有一个节点
//            if (root.left == null && root.right == null) {
//                root = null;
//                return;
//            }
            //去找到targetNode的父节点
            Node parent = searchParent(value);
            //查找到的节点没有父节点
            if (parent == null) {
                root = null;
                return;
            }
            //如果要删除的节点是叶子结点
            if (targetNode.left == null && targetNode.right == null) {
                //判断targetNode是父节点的左子节点，还是右子节点
                if (parent.left != null && parent.left.value == value) {//是左子节点
                    parent.left = null;
                }else if (parent.right != null && parent.right.value == value) {//是右子节点
                    parent.right = null;
                }
            }else if (targetNode.left != null &&targetNode.right != null) {//当前节点的左右子树都不为空
                int minValue = delRightTreeMin(targetNode.right);
                targetNode.value = minValue;
            }else {//删除只有一棵子树的情况
                //如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    if (parent != null) {//判断节点是否有父节点
                        //如果targetNode是parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        }else {//如果targetNode是parent的右子节点
                            parent.right = targetNode.left;
                        }
                    }else {
                        root = targetNode.left;
                    }
                }else {//如果要删除的节点有右子节点
                    if (parent != null) {//判断节点是否有父节点
                        //如果targetNode是parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        }else {//如果targetNode是parent的右子节点
                            parent.right = targetNode.right;
                        }
                    }else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }
    
}
